package com.chj.gaoji.class10;

import java.util.Arrays;
import java.util.HashMap;

public class Code05_TallestBillboard {

	public static int tallestBillboard(int[] rods) {
		// key 集合对的某个差
		// value 满足差值为key的集合对中，最好的一对，较小集合的累加和
		// 较大 -> value + key
		HashMap<Integer, Integer> dp = new HashMap<>(), cur;
		dp.put(0, 0);// 空集 和 空集
		for (int input : rods) {
			if (input != 0) {
				cur = new HashMap<>(dp); // 考虑x之前的集合差值状况拷贝下来
				for (int diff : cur.keySet()) {
					int diffMoreAndMinSum = cur.get(diff); // 最好的一对，较小集合的累加和
					// x决定放入，比较大的那个
					dp.put(diff + input, Math.max(diffMoreAndMinSum, dp.getOrDefault(input + diff, 0)));
					// x决定放入，比较小的那个
					// 新的差值 Math.abs(x - d)
					// 之前差值为Math.abs(x - d)，的那一对，就要和这一对，决策一下
					// 之前那一对，较小集合的累加和diffXD
					int diffXD = dp.getOrDefault(Math.abs(input - diff), 0);
					if (diff >= input) { // x决定放入比较小的那个, 但是放入之后，没有超过这一对较大的那个
						dp.put(diff - input, Math.max(diffMoreAndMinSum + input, diffXD));
					} else { // x决定放入比较小的那个, 但是放入之后，没有超过这一对较大的那个
						dp.put(input - diff, Math.max(diffMoreAndMinSum + diff, diffXD));
					}
				}
			}
		}

		return dp.get(0);
	}

	public static int tallestBillboard02(int[] rods) {
		if (rods == null || rods.length < 2) {
			return 0;
		}
		int len = rods.length;

		int sum = 0;
		for (int si = 0; si < len; si++) {
			sum += rods[si];
		}

		// 定义状态方程：dp[i][j]: 表示用前i+1个钢筋，形成两个互斥子集合的差为j，子集合的和最大。
		// 例如【1，2，3，6】, 我们用前4个钢筋，差为1的两个子集合有很多，dp[3][1], 如{1}和{2}, {2}和{3}
		// {2,3}和{6}, 最大和的两个子集合，应该是{2,3}和{6}, 它们的和为11， 所以dp[3][1] = 11;
		// 我们的目标是找到dp[n][0]的值。

		int[][] dp = new int[len][sum + 1];
		dp[0][rods[0]] = rods[0]; // 初始化，只有第1个钢筋的情况下，能够形成差为rods[0]的两个子集合，它们的和也是自身

		int preSum = rods[0];

		for (int i = 1; i < len; i++) {
			for (int j = 0; j <= preSum; j++) {
				// 状态数组里有一些无效的值，如果两个子集的差为j, 它们的和肯定大于j。 这种dp值是无效的，不应该
				// 用来更新dp[i]的值
				if (dp[i - 1][j] < j)
					continue;
				// std::cout << "j = " << j << std::endl;

				// 更新dp[i][j], 有3种情况；
				// 1. 元素i不放入任一一个子集合， 那么差与和都不更新
				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);

				// 2. 元素i放入和更大的子集合，那么子集合差就会更大，我们应该更新dp[i][j+rods[i]]
				int k = j + rods[i];
				dp[i][k] = Math.max(dp[i][k], dp[i - 1][j] + rods[i]);

				// 3. 元素i放入和更小的子集合，那么子集合的差就会变小, 我们应该更新dp[i][j-rods[i]]
				k = Math.abs(j - rods[i]);
				dp[i][k] = Math.max(dp[i][k], dp[i - 1][j] + rods[i]);
			}

			preSum += rods[i];
		}

		return dp[len - 1][0] / 2;
	}

//	作者：kuangjianping
//	链接：https://leetcode-cn.com/problems/tallest-billboard/solution/dong-tai-gui-hua-ke-yi-kan-cheng-01bei-bao-de-bian/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static int tallestBillboard03(int[] rods) {
		if (rods == null || rods.length < 2) {
			return 0;
		}
		int n = rods.length;

		int m = 0;
		for (int si = 0; si < n; si++) {
			m += rods[si];
		}
		int[][] dp = new int[n + 1][m + 1];

		for (int i = 1; i <= n; ++i)
			for (int j = 0; j <= m; ++j) {
				if (dp[i - 1][j] >= j) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);

					int k = j + rods[i - 1];
					dp[i][k] = Math.max(dp[i][k], dp[i - 1][j] + rods[i - 1]);

					k = Math.abs(j - rods[i - 1]);
					dp[i][k] = Math.max(dp[i][k], dp[i - 1][j] + rods[i - 1]);
				}
			}
		return dp[n][0] / 2;
	}

//	作者：ck0825
//	链接：https://leetcode-cn.com/problems/tallest-billboard/solution/leetcode-956-dong-tai-gui-hua-qiu-jie-by-ck0825/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	private static int ans = 0;

	public static int tallestBillboard04(int[] rods) {
		int len = rods.length;
		if (len == 0 || len == 1)
			return 0;
		// 计算钢筋的总和
		int remain = 0;
		for (int i : rods) {
			remain += i;
		}
		Arrays.sort(rods);
		// 从最大的钢筋开始处理
		billBoardHelper(rods, rods.length - 1, remain, 0, 0);
		return ans;
	}

	private static void billBoardHelper(int[] rods, int i, int remain, int left, int right) {
		// 若左右相等，则进行比较
		if (left == right) {
			ans = Math.max(ans, left);
		}
		/*
		 * 剪枝：
		 * 
		 * 1.剩余筹码 s 不足以将 l、r 的差值补充时，提前返回 2.剩余筹码 s 和 l、r 的总和比当前最大和 ans
		 * 还要少时，也就是说无论怎么凑得到的最终和也不会比 ans 大，提前返回 //
		 * https://qxddl.blog.csdn.net/article/details/107301221 // 剪枝 //
		 * 直觉是从第一个数开始遍历，然后分别给左边，右边或者不给，两边相等的时候就记录当前的最大值 // // 优化： //
		 * 1、两边的绝对值代表两边相差的高度，如果剩下的数<相差的高度，就证明后面不再可能有两边相等的机会了； //
		 * 2、两边的高度+剩下的高度如果小于等于2*ans，证明就算剩下的高度可以凑，平分之后还是最多比ans小，去掉
		 */
		if (Math.abs(left - right) > remain || left + right + remain <= ans * 2 || i < 0) {
			return;
		}

		// 开始对第i根钢筋进行处理，remain减去rods[i]
		remain -= rods[i];
		// 放左边
		billBoardHelper(rods, i - 1, remain, left + rods[i], right);
		// 放右边
		billBoardHelper(rods, i - 1, remain, left, right + rods[i]);
		// 不放
		billBoardHelper(rods, i - 1, remain, left, right);
	}

//作者：chen-zi-tao
//链接：https://leetcode-cn.com/problems/tallest-billboard/solution/dfsjian-zhi-by-chen-zi-tao/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
		int[] rods = new int[] { 1, 2, 3, 6 };
		System.out.println(tallestBillboard(rods));
		System.out.println(tallestBillboard02(rods));
		System.out.println(tallestBillboard03(rods));
		System.out.println(tallestBillboard04(rods));
	}
}
